﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AI_Game
{
    class GodAI
    {
        int[,] s_matrix;
        int[,] data;
        int maxFreeVer;//tong so dinh nhieu nhat co the di
        int[] L; //luu dinh da di qua
        int[] aLine;//chon 1 line
        bool hasLine;
        int countALine;
        int count;// dem dinh da di qua
        int xCurrent;
        int yCurrent;
        int verCurrent;
        int[] aMinLine;
        int countAMinLine;
        bool isConnectGrap;

        public GodAI(){}
        public GodAI(int[,] data, int xC, int yC)
        {
            xCurrent = xC;
            yCurrent = yC;
            verCurrent = yCurrent * 11 + xCurrent;
            maxFreeVer = 0;
            count = 0;
            isConnectGrap = false;
            hasLine = false;
            countALine = 0;
            s_matrix = new int[121, 121];
            L = new int[121];
            aLine = new int[121];

            //Cho tim duong di ngan nhat
            aMinLine = new int[121];
            countAMinLine = 0;
            //---

            this.data = data;

        }
        public int[] GetLine(ref int countLine)
        {
            countLine = countALine;
            return aLine;
        }
        public void Go(ref int x, ref int y)
        {
            if (hasLine)
            {
                int ll = aLine[1];
                xCurrent = aLine[1] % 11;
                yCurrent = aLine[1] / 11;
                x = xCurrent;
                y = yCurrent;
            }
            else
            { 
                //YOU LOSE ^^!
                x = 0;
                y = 0;
                System.Windows.Forms.MessageBox.Show("Het duong roi :)");
            }
        }
        public int[] FindLine2(int x1, int y1, int x2, int y2, ref int count)
        {
            CreateMatrix();
            ClearVertice();

            int D = y1 * 11 + x1;
            int C = y2 * 11 + x2;

            CheckConnectGraph(D, C);
            if (!isConnectGrap)
            {
                System.Windows.Forms.MessageBox.Show("Khong di duoc :)");
                count = 0;
            }
            else
            {
                Dijkstra(D, C);
                count = countAMinLine;
            }
            return aMinLine;
        }
        public void FindLine()
        {
            hasLine = false;     
            count = 0;
            countALine = 0;
            verCurrent = yCurrent * 11 + xCurrent;
           

            CreateMatrix();
            ClearVertice();

            L[count] = verCurrent;
            Try(verCurrent, count + 1);
        }
        int CheckLevelVertice(int ver)
        {
            int countLevel = 0;
            for (int i = 0; i < 121; i++)
            {
                if (s_matrix[ver, i] == 1)
                {
                    countLevel++;
                }
            }
            return countLevel;        
        }
        void CheckFreeVertice(int ver)// kiem tra xem tai thoi diem hien tai co the di them bao nhieu o
        {
            count = 0;
            countALine = 0;
            verCurrent = yCurrent * 11 + xCurrent;


            CreateMatrix();
            ClearVertice();

            L[count] = verCurrent;
            Try(verCurrent, count + 1);

            maxFreeVer = countALine;
        }
        void ClearVertice()
        {         
            for (int i = 0; i < 121; i++)
            {
                L[i] = 9999;
            }
        }
        bool CheckVertice(int ver)
        {
            for (int i = 0; i < 121; i++)
            {
                if (L[i] == ver)
                    return false;
            }
            return true;
        }
        void Try(int vStart, int count)
        {
            {                
                for (int i = 0; i < 121; i++)
                {
                    if (s_matrix[vStart, i] == 1 && CheckVertice(i))
                    {                    
                        L[count] = i;
                        //Trace.WriteLine("L[" + count.ToString() + "] = " + L[count].ToString());
                        Try(i, count + 1);
                    }   
                }
                if (countALine < count && count > 1)
                {
                    hasLine = true;
                    for (int i = 0; i < 121; i++)
                    {
                        aLine[i] = L[i];
                    }
                    countALine = count;
                }
            }
        }

        void CheckConnectGraph(int vStart, int vEnd)
        {
            isConnectGrap = false;
            count = 0;
            verCurrent = vStart;

            L[count] = verCurrent;

            TryCheck(vStart, vEnd, count + 1);
        }

        void TryCheck(int vStart, int vEnd, int count)
        {
            for (int i = 0; i < 121; i++)
            {
                if (isConnectGrap)
                {
                    break;
                }
                if (s_matrix[vStart, i] == 1 && CheckVertice(i))
                {
                    if (i == vEnd)
                    {
                        isConnectGrap = true;
                        break;
                    }
                    else
                    {
                        L[count] = i;
                        TryCheck(i, vEnd, count + 1);
                    }
                }
            }
        }

        void Dijkstra(int D, int C)
        {
            char[] DanhDau = new char[121];

            int[] Nhan = new int[121];
            int[] Truoc = new int[121];
            int XP, min;

            /*int imin = std::numeric_limits<int>::min(); // minimum value
              int imax = std::numeric_limits<int>::max();
              std::numeric_limits is a template type which can be instantiated with other types:

              float fmin = std::numeric_limits<float>::min(); // minimum positive value
              float fmax = std::numeric_limits<float>::max();*/


            for (int i = 0; i < 121; i++)
            {
                Nhan[i] = int.MaxValue;
                DanhDau[i] = '0';
                Truoc[i] = D;
            }
            Nhan[D] = 0;
            DanhDau[D] = '1';
            XP = D;
            while (XP != C)
            {
                for (int j = 0; j < 121; j++)
                {
                    if (s_matrix[XP, j] > 0 && Nhan[j] > s_matrix[XP, j] + Nhan[XP] && DanhDau[j] == '0')
                    {
                        Nhan[j] = s_matrix[XP, j] + Nhan[XP];
                        Truoc[j] = XP;
                    }
                }
                min = int.MaxValue;
                for (int j = 0; j < 121; j++)
                {
                    if (min > Nhan[j] && DanhDau[j] == '0')
                    {
                        min = Nhan[j];
                        XP = j;
                    }
                }
                DanhDau[XP] = '1';
            }

            int[] SavePath = new int[121];
            int sp = 0;

            Trace.WriteLine("Duong Di Ngan Nhat La:" + Nhan[C].ToString());
            Trace.WriteLine((C + 1).ToString() + " <- " + (Truoc[C] + 1).ToString());
            SavePath[sp++] = C;
            SavePath[sp++] = Truoc[C];
            int k = Truoc[C];
            while (k != D)
            {
                k = Truoc[k];
                Trace.WriteLine(" <- " + (k + 1).ToString());
                SavePath[sp++] = k;
            }

            countAMinLine = sp;

            for (k = 0; k < countAMinLine; k++)
            {
                aMinLine[k] = SavePath[--sp];
            }
            verCurrent = C;
        }

        private void CreateMatrix()
        {
            for (int i = 0; i < 121; i++)
            {
                int iX = i % 11;
                int iY = i / 11;
                if (data[iX, iY] != 0 && i != verCurrent)
                {
                    for (int j = 0; j < 121; j++)
                    {

                        s_matrix[i, j] = 0;
                    }
                }
                else
                {
                    for (int j = 0; j < 121; j++)
                    {
                        if (i == j)
                        {
                            s_matrix[i, j] = 0;
                        }
                        else
                        {
                            int jX = j % 11;
                            int jY = j / 11;
                            if (data[jX, jY] == 0)
                            {
                                if (iX == jX && ((iY == jY - 1) || (iY == jY + 1)))
                                {
                                    s_matrix[i, j] = 1;
                                }
                                else if (iY == jY && ((iX == jX - 1) || (iX == jX + 1)))
                                {
                                    s_matrix[i, j] = 1;
                                }
                                else
                                {
                                    s_matrix[i, j] = 0;
                                }
                            }
                            else
                            {
                                s_matrix[i, j] = 0;
                            }
                        }
                    }
                }
            }
        }
    }
}
